package com.fang.offer.array;

/**
 * <p>
 * 时间限制：1秒 空间限制：32768K
 * </p>
 * <p>
 * 本题知识点： 查找
 * </p>
 * <p>
 * 题目描述 在一个二维数组中， 每一行都按照从左到右递增的顺序排序， 每一列都按照从上到下递增的顺序排序。
 * 请完成一个函数，输入这样的一个二维数组和一个整数， 判断数组中是否含有该整数。
 * </p>
 */
public class OfferArrayFind {

	public static void main(String[] args) {
		OfferArrayFind find = new OfferArrayFind();
		int[][] array = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } };
		System.out.println(find.find(7, array));
	}

	public boolean find(int target, int[][] array) {
		if (array == null)
			return false;
		int width = array[0].length;
		int height = array.length;
		int i = 0;
		int j = height - 1;
		while ((i < width) && (j >= 0)) {
			if (array[i][j] == target)
				return true;
			if (array[i][j] > target) {
				// 纵列-1
				j--;
				continue;
			}
			if (array[i][j] < target) {
				// 行数+1
				i++;
				continue;
			}
		}
		return false;
	}
}
